package site.wanjiahao.recursion;

public class UpStair {

    // 上台阶
    public int upStair1(int n) {
        if (n < 3) return n;
        // 对于第n阶台阶，有两种走法，跳一步或者跳两步
        return upStair1(n - 1) + upStair1(n - 2);
    }

    // 非递归
    public int upStair2(int n) {
        int first = 1;
        int second = 2;
        while (n-- > 2) {
            second = first + second;
            first = second - first;
        }
        return second;
    }

}
